Zhongshan ZHANG Yuning CHEN Yuejin TAN Jungang YAN
This paper presents a non-crossover and multi-mutation based genetic algorithm (NMGA) for the Flexible Job-shop Scheduling problem (FJSP) with the criterion to minimize the maximum completion time (makespan). Aiming at the characteristics of FJSP, three mutation operators based on operation sequence coding and machine assignment coding are proposed: flip, slide, and swap. Meanwhile, the NMGA framework, coding scheme, as well as the decoding algorithm are also specially designed for the FJSP. In the framework, recombination operator crossover is not included and a special selection strategy is employed. Computational results based on a set of representative benchmark problems were provided. The evidence indicates that the proposed algorithm is superior to several recently published genetic algorithms in terms of solution quality and convergence ability.
Patchaikani SINDHUJA Yoshihiko KUWAHARA Kiyotaka KUMAKI Yoshiyuki HIRAMATSU
In this paper, a vehicular antenna design scheme that considers vehicular body effects is proposed. A wire antenna for the global positioning system (GPS) and long-term evolution (LTE) systems is implemented on a plastic plate and then mounted on a windshield of the vehicle. Common outputs are used to allow feed sharing. It is necessary to increase the GPS right-hand circularly polarization (RHCP) gain near the zenith and to reduce the axis ratio (AR). For LTE, we need to increase the horizontal polarization (HP) gain. In addition, for LTE, multiband characteristics are required. In order to achieve the specified performance, the antenna shape is optimized via a Pareto genetic algorithm (PGA). When an antenna is mounted on the body, antenna performance changes significantly. To evaluate the performance of an antenna with complex shape mounted on a windshield, a commercial electromagnetic simulator (Ansoft HFSS) is used. To apply electromagnetic results output by HFSS to the PGA algorithm operating in the MATLAB environment, a MATLAB-to-HFSS linking program via Visual BASIC (VB) script was used. It is difficult to carry out the electromagnetic analysis on the entire body because of the limitations of the calculating load and memory size. To overcome these limitations, we consider only that part of the vehicle's body that influences antenna performance. We show that a series of optimization steps can minimize the degradation caused by the vehicle`s body. The simulation results clearly show that it is well optimized at 1.575GHz for GPS, and 0.74 ∼ 0.79GHz and 2.11 ∼ 2.16GHz for LTE, respectively.
Taiki IIDA Daisuke ANZAI Jianqing WANG
To improve the performance of capsule endoscope, it is important to add location information to the image data obtained by the capsule endoscope. There is a disadvantage that a lot of existing localization techniques require to measure channel model parameters in advance. To avoid such a troublesome pre-measurement, this paper pays attention to capsule endoscope localization based on an electromagnetic imaging technology which can estimate not only the location but also the internal structure of a human body. However, the electromagnetic imaging with high resolution has huge computational complexity, which should prevent us from carrying out real-time localization. To ensure the accurate real-time localization system without pre-measured model parameters, we apply genetic algorithm (GA) into the electromagnetic imaging-based localization method. Furthermore, we evaluate the proposed GA-based method in terms of the simulation time and the location estimation accuracy compared to the conventional methods. In addition, we show that the proposed GA-based method can perform more accurately than the other conventional methods, and also, much less computational complexity of the proposed method can be accomplished than a greedy algorithm-based method.
Gang DENG Hong WANG Zhenghu GONG Lin CHEN Xu ZHOU
Address configuration is a key problem in data center networks. The core issue of automatic address configuration is assigning logical addresses to the physical network according to a blueprint, namely logical-to-device ID mapping, which can be formulated as a graph isomorphic problem and is hard. Recently years, some work has been proposed for this problem, such as DAC and ETAC. DAC adopts a sub-graph isomorphic algorithm. By leveraging the structure characteristic of data center network, DAC can finish the mapping process quickly when there is no malfunction. However, in the presence of any malfunctions, DAC need human effort to correct these malfunctions and thus is time-consuming. ETAC improves on DAC and can finish mapping even in the presence of malfunctions. However, ETAC also suffers from some robustness and efficiency problems. In this paper, we present GA-MAP, a data center networks address mapping algorithm based on genetic algorithm. By intelligently leveraging the structure characteristic of data center networks and the global search characteristic of genetic algorithm, GA-MAP can solve the address mapping problem quickly. Moreover, GA-MAP can even finish address mapping when physical network involved in malfunctions, making it more robust than ETAC. We evaluate GA-MAP via extensive simulation in several of aspects, including computation time, error-tolerance, convergence characteristic and the influence of population size. The simulation results demonstrate that GA-MAP is effective for data center addresses mapping.
Nguyen Ngoc BINH Pham Van HUONG Bui Ngoc HAI
Optimizing embedded software is a problem having scientific and practical signification. Optimizing embedded software can be done in different phases of the software life cycle under different optimal conditions. Most studies of embedded software optimization are done in forward engineering and these studies have not given an overall model for the optimization problem of embedded software in both forward engineering and reverse engineering. Therefore, in this paper, we propose a new approach to embedded software optimization based on reverse engineering. First, we construct an overall model for the embedded software optimization in both forward engineering and reverse engineering and present a process of embedded software optimization in reverse engineering. The main idea of this approach is that decompiling executable code to source code, converting the source code to models and optimizing embedded software under different levels such as source code and model. Then, the optimal source code is recompiled. To develop this approach, we present two optimization techniques such as optimizing power consumption of assembly programs based on instruction schedule and optimizing performance based on alternating equivalent expressions.
Xiaoqiang ZHANG Xuesong WANG Yuhu CHENG
To ensure the security of image transmission, this paper presents a new image encryption algorithm based on a genetic algorithm (GA) and a piecewise linear chaotic map (PWLCM), which adopts the classical diffusion-substitution architecture. The GA is used to identify and output the optimal encrypted image that has the highest entropy value, the lowest correlation coefficient among adjacent pixels and the strongest ability to resist differential attack. The PWLCM is used to scramble pixel positions and change pixel values. Experiments and analyses show that the new algorithm possesses a large key space and resists brute-force, statistical and differential attacks. Meanwhile, the comparative analysis also indicates the superiority of our proposed algorithm over a similar, recently published, algorithm.
A renal biopsy is a procedure to get a small piece of kidney for microscopic examination. With the development of tissue sectioning and medical imaging techniques, microscope renal biopsy image sequences are consequently obtained for computer-aided diagnosis. This paper proposes a new context-based segmentation algorithm for acquired image sequence, in which an improved genetic algorithm (GA) patching method is developed to segment different size target. To guarantee the correctness of first image segmentation and facilitate the use of context information, a boundary fusion operation and a simplified scale-invariant feature transform (SIFT)-based registration are presented respectively. The experimental results show the proposed segmentation algorithm is effective and accurate for renal biopsy image sequence.
Due to the recent development of underlying hardware technology and improvement in installing environments, public display has been becoming more common and attracting more attention as a new type of signage. Any signage is required to make its content more attractive to its viewers by evaluating the current attractiveness on the fly, in order to deliver the message from the sender more effectively. However, most previous methods for public display require time to reflect the viewers' evaluations. In this paper, we present a novel system, called Mood-Learning Public Display, which automatically adapts its content design. This system utilizes viewers' involuntary behaviors as a sign of evaluation to make the content design more adapted to local viewers' tastes evolutionarily on site. The system removes the current gap between viewers' expectations and the content actually displayed on the display, and makes efficient mutual transmission of information between the cyberworld and the reality.
In this paper, a one-class Naïve Bayesian classifier (One-NB) for detecting toll frauds in a VoIP service is proposed. Since toll frauds occur irregularly and their patterns are too diverse to be generalized as one class, conventional binary-class classification is not effective for toll fraud detection. In addition, conventional novelty detection algorithms have struggled with optimizing their parameters to achieve a stable detection performance. In order to resolve the above limitations, the original Naïve Bayesian classifier is modified to handle the novelty detection problem. In addition, a genetic algorithm (GA) is employed to increase efficiency by selecting significant variables. In order to verify the performance of One-NB, comparative experiments using five well-known novelty detectors and three binary classifiers are conducted over real call data records (CDRs) provided by a Korean VoIP service company. The experimental results show that One-NB detects toll frauds more accurately than other novelty detectors and binary classifiers when the toll frauds rates are relatively low. In addition, The performance of One-NB is found to be more stable than the benchmark methods since no parameter optimization is required for One-NB.
This paper introduces a comparison of three automatic gait generation methods for quadruped robots: GA (Genetic Algorithm), GP (genetic programming) and CPG (Central Pattern Generator). It aims to provide a useful guideline for the selection of gait generation methods. GA-based approaches seek to optimize paw locus in Cartesian space. GP-based techniques generate joint trajectories using regression polynomials. The CPGs are neural circuits that generate oscillatory output from an input coming from the brain. Optimizations for the three proposed methods are executed and analyzed using a Webots simulation of the quadruped robot built by Bioloid. The experimental comparisons and analyses provided herein will be an informative guidance for research of gait generation method.
Ittetsu TANIGUCHI Kohei AOKI Hiroyuki TOMIYAMA Praveen RAGHAVAN Francky CATTHOOR Masahiro FUKUI
A fast and accurate architecture exploration for high performance and low energy VLIW data-path is proposed. The main contribution is a method to find Pareto optimal FU structures, i.e., the optimal number of FUs and the best instruction assignment for each FU. The proposed architecture exploration method is based on GA and enables the effective exploration of vast solution space. Experimental results showed that proposed method was able to achieve fast and accurate architecture exploration. For most cases, the estimation error was less than 1%.
In this letter, we present a novel interference-aware clustering scheme for cell broadcasting service. The proposed approach is based on a genetic algorithm for re-clustering. Using the genetic algorithm, the suggested method efficiently re-clusters the user nodes when the relays fail in receiving the cell broadcasting message from the base station. The simulation results exhibit that the proposed clustering scheme can maintain much higher capacity than the conventional clustering scheme in the cases of relay outage. The re-clustering method based on genetic algorithm also shows lower complexity than the re-clustering approach based on exhaustive search.
Guifang SHAO Wupeng HONG Tingna WANG Yuhua WEN
An improved genetic algorithm is employed to optimize the structure of (C60)N (N≤25) fullerene clusters with the lowest energy. First, crossover with variable precision, realized by introducing the hamming distance, is developed to provide a faster search mechanism. Second, the bit string mutation and feedback mutation are incorporated to maintain the diversity in the population. The interaction between C60 molecules is described by the Pacheco and Ramalho potential derived from first-principles calculations. We compare the performance of the Improved GA (IGA) with that of the Standard GA (SGA). The numerical and graphical results verify that the proposed approach is faster and more robust than the SGA. The second finite differential of the total energy shows that the (C60)N clusters with N=7, 13, 22 are particularly stable. Performance with the lowest energy is achieved in this work.
We designed multilayer wavelength-selective reflector films by stacking thin-films of transparent polymer. The optimum structure of the multilayer is determined using a combination of characteristic matrix method and a version of genetic algorithm. Such multilayer films can be used in LCD devices to enhance the color saturation of the display.
Kazi OBAIDULLAH Constantin SIRITEANU Shingo YOSHIZAWA Yoshikazu MIYANAGA
Genetic algorithm (GA) is now an important tool in the field of wireless communications. For multiple-input/multiple-output (MIMO) wireless communications system employing spatial multiplexing transmission, we evaluate the effects of GA parameters value on channel parameters in fading channels. We assume transmit-correlated Rayleigh and Rician fading with realistic Laplacian power azimuth spectrum. Azimuth spread (AS) and Rician K-factor are selected according to the measurement-based WINNER II channel model for several scenarios. Herein we have shown the effects of GA parameters and channel parameters in different WINNER II scenarios (i.e., AS and K values) and rank of the deterministic components. We employ meta GA that suitably selects the population (P), generation (G) and mutation probability (pm) for the inner GA. Then we show the cumulative distribution function (CDF) obtain experimentally for the condition number C of the channel matrix H. It is found that, GA parameters depend on the channel parameters, i.e., GA parameters are the functions of the channel parameters. It is also found that for the poorer channel conditions smaller GA parameter values are required for MIMO detection. This approach will help to achieve maximum performance in practical condition for the lower numerical complexity.
Many applications of wireless sensor networks (WSNs) require secure communication. The tree-based key management scheme, which is a symmetric key scheme, provides backward and forward secrecy. The sensor nodes in the communication group share a secret key for encrypting messages. When the sensor nodes are added to or evicted from the group, the group key has to be updated by sending rekeying messages. In this paper, we propose a method of key tree structure (KTS) generation by considering the addition and eviction ratio of sensor nodes to reduce the number of rekeying messages, which is influenced by the structure of the tree. For this, we define an extension of an existing tree structure such as a binary or ternary tree and generate KTS using an A* algorithm. To reduce the energy consumed by the message transmission, we also exploit genetic algorithm (GA) to build a secure communication group by considering the KTS. In the paper, we show the effectiveness of the proposed method compared with the existing structure via the simulation in terms of memory usage, the number of rekeying messages and energy consumption.
Ryota KOUZUKI Toshimichi SAITO
This paper studies the simple dynamic binary neural network characterized by the signum activation function, ternary weighting parameters and integer threshold parameters. The network can be regarded as a digital version of the recurrent neural network and can output a variety of binary periodic orbits. The network dynamics can be simplified into a return map, from a set of lattice points, to itself. In order to store a desired periodic orbit, we present two learning algorithms based on the correlation learning and the genetic algorithm. The algorithms are applied to three examples: a periodic orbit corresponding to the switching signal of the dc-ac inverter and artificial periodic orbit. Using the return map, we have investigated the storage of the periodic orbits and stability of the stored periodic orbits.
Gina KWON Keum-Cheol HWANG Joon-Young PARK Seon-Joo KIM Dong-Hwan KIM
A hybrid approach for the synthesis of square thinned arrays with low sidelobes is presented. The proposed method combines the advantages of a genetic algorithm and combinatorial technique-cyclic difference sets (CDSs). The peak sidelobe level (PSL) and the thinning factor are numerically evaluated to show the effectiveness and reliability of the proposed hybrid method. In the proposed GA-enhanced square arrays with the DS and the best CDS, reductions of the PSL, of 4.16 dB and 2.45 dB, respectively, were achieved as compared to the results of conventional rectangular DS and CDS arrays.
Yoichi NAGAO Shinichi NAKANO Akifumi HOSHINO Yasushi KANETA Toshiyuki KITA Masakazu OKAMOTO
The authors propose a method to make a movement plan for relocation of the railway cars in preparation for the final assembly. It obtains solution through three steps. The first step is to extract the order constraints between the movements of the railway cars based on their locations before and after relocation. The second step is to introduce the movement which puts a railway car into another location temporarily, in order to avoid a deadlock in the movements. And the final step is to obtain the movement order for carrying out the relocation in the shortest time in accordance with the calculated order constraints by using the genetic algorithm (GA). The order constraints are resolved in advance and therefore the movement order can easily be decided by GA. As the result, the developed system takes time shorter than an expert for planning the relocation.
The broadcast scheduling problem (BSP) in wireless ad-hoc networks is a well-known NP-complete combinatorial optimization problem. The BSP aims at finding a transmission schedule whose time slots are collision free in a wireless ad-hoc network with time-division multiple access (TDMA). The transmission schedule is optimized for minimizing the frame length of the node transmissions and maximizing the utilization of the shared channel. Recently, many metaheuristics can optimally solve smaller problem instances of the BSP. However, for complex problem instances, the computation of metaheuristics can be quite time and memory consuming. In this work, we propose a greedy genetic algorithm for solving the BSP with a large number of nodes. We present three heuristic genetic operators, including a greedy crossover and two greedy mutation operators, to optimize both objectives of the BSP. These heuristic genetic operators can generate good solutions. Our experiments use both benchmark data sets and randomly generated problem instances. The experimental results show that our genetic algorithm is effective in solving the BSP problem instances of large-scale networks with 2,500 nodes.